{
 "metadata": {
  "language": "Julia",
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Introduction"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Julia is a dynamically-typed language. As with all dynamically-typed languages, users sometimes miss the option for static checking. As my master's project, I wrote TypeCheck.jl, which is a package for type-based static analysis of Julia code. The checks it implements work on any named function. The package has checks for stability of function return types, stability of variable types inside loops, and for potential `NoMethodError`s. TypeCheck.jl is available in the Julia package manager, and was announced on the julia-users mailing list."
     ]
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "A Summary of Julia"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Julia is a new language designed for technical computing.\n",
      "It is as easy to use and general-purpose as Python,\n",
      "but designed for fast computation, low-level control, and easy to express math.\n",
      "Julia is high-performance, dynamically-typed, and JIT-compiled.\n",
      "It is not focused on new ideas, but on executing existing ideas well, with a focus on being practical and approachable.\n",
      "As a language, some of Julia's distinctive features include multiple dispatch, first-class types, and Lisp-style macros."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "The Julia Type System"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Every value in Julia has a type; variables contain values, but do not themselves have types.\n",
      "Types are arranged into a hierarchy of abstract and concrete types.\n",
      "Abstract types can have subtypes, but cannot be instantiated and do not have properties.\n",
      "Concrete types can be instantiated and have zero or more properties, but cannot have subtypes.\n",
      "Every type has a super type.\n",
      "At top of the hierarchy is the `Any` type; the super type of `Any` is `Any`.\n",
      "\n",
      "In Julia, types are first-class; types are of type DataType, which is itself of type DataType.\n",
      "Types are used for inference, optimization, dispatch, and documentation, but not for type checking.\n",
      "Because Julia still works (but more slowly) without any type inference, all of the type inference is implemented in the language.\n",
      "\n",
      "Types can also take parameters; these can be types or `Int`s. For example, `Array{T,N}` is parameterized by the element type and the number of dimensions. Instances of the same type with different type parameters (say `Array{Int,6}` and `Array{Number,4}`) are never subtypes of one another.\n",
      "\n",
      "To define a type, you use the `type` keyword:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "type Point{T <: Number}\n",
      "    x::T\n",
      "    y::T\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The Point{T} type will have two properties, `x` and `y`. For any `Point`, the two properties will share a type, and their type will be a subtype of `Number`. From the definition, we also know that when a `Point` is represented in memory, `x` will precede `y`. Julia types are laid out in memory in a way compatible with C structs, which made implementing Julia's C calling functionality easier (and the result more efficient)."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Introspection in Julia"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Julia has admirable introspection and reflection abilities, which are very useful for writing static analysis.\n",
      "For any named function, you can get a type-inferred AST with a simple function call:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function foo(x::Int)\n",
      "    z = x + 5\n",
      "    return 2 * z\n",
      "end\n",
      "\n",
      "code_typed(foo,(Int,))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "1-element Array{Any,1}:\n",
        " :($(Expr(:lambda, {:x}, {{:z},{{:x,Int64,0},{:z,Int64,18}},{}}, quote  # In[2], line 2:\n",
        "        z = top(box)(Int64,top(add_int)(x::Int64,5))::Int64 # line 3:\n",
        "        return top(box)(Int64,top(mul_int)(2,z::Int64))::Int64\n",
        "    end)))"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The `code_typed` function takes a function and a method signature.\n",
      "Every named function is a generic function: it has one or more methods, each with their own type signature.\n",
      "Julia uses multiple dispatch, which means that it considers the type, number, and order of all the arguments to pick the best match to a call.\n",
      "\n",
      "`code_typed` returns an  untyped `Array` of `Expr`s, the type that represents a node of the Julia AST.\n",
      "For many invocations, this `Array` will only have one element. When the provided signature could match more than one existing method, all possible matches are returned. \"Possible\" matches occur when you pass an abstract type as part of the signature and some methods of the function accept subtypes of that type. The type of an actual value is always concrete, so the method that would actually get called would vary."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "e = code_typed(foo,(Int,))[1] #Julia indexes from 1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 3,
       "text": [
        ":($(Expr(:lambda, {:x}, {{:z},{{:x,Int64,0},{:z,Int64,18}},{}}, quote  # In[2], line 2:\n",
        "        z = top(box)(Int64,top(add_int)(x::Int64,5))::Int64 # line 3:\n",
        "        return top(box)(Int64,top(mul_int)(2,z::Int64))::Int64\n",
        "    end)))"
       ]
      }
     ],
     "prompt_number": 3
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "An `Expr` has three fields: `head`, `args`, and `typ`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "names(e)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "3-element Array{Symbol,1}:\n",
        " :head\n",
        " :args\n",
        " :typ "
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "* `head` is a symbol indicating the type of expression. For `Expr`s returned by `code_typed`, this will be `:lambda`. (In Julia, `:foo` is a way to write \"the symbol `foo`\".)\n",
      "* `typ` is the return type of the method.\n",
      "* `args` is an `Array` of `Array`s. It contains information about the variables (local, arguments, captured) and body of the function. I'll explain more about the structure of `args` as needed in the rest of this document."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "The Base Library"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Julia's standard library is carefully written: changes happen in pull requests that get code review, good API design is an important goal, and there are knowledgeable contributors who pay attention to the details of numerical methods. Despite this care, my static analysis functions still found a few actual problems."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "New Type Annotation"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The `toq` function is used with `tic` for timing code execuition. `tic()` saves a timestamp, and `toq()` retrieves it and finds the difference to the current time. Because the storage used for the timestamp is untyped, `toq()` has a return type of `Any`. It actually always returned a value of type `Float64`. I added a type annotation to the value retrieve from storage, which is always `UInt64`, which fixed the type inference. This change was merged in to Julia's base library; it was [pull request #4148](https://github.com/JuliaLang/julia/pull/4148)."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Symbol Clean Up"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The standard library lives in the `Base` module. Part of running a check on every function in `Base` is reflecting on the module to discover the functions. In order to make a function easily publicly available, a module puts the relevant function names in an `export` statement. Julia does not warn or throw an error when an undefined symbol is exported. I found an instance of this error and fixed it in [pull request #5542](https://github.com/JuliaLang/julia/pull/5542)."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Calling `QR` with Incorrect Array Dimension"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In the course of testing `NoMethodError` detection, I found that `qrfact` had a method that failed: `qrfact(x::Number)`. Ignoring any semantic meaning, the implementation would clearly always throw an error."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "qrfact(x::Number) = QR(fill(one(x), 1, 1), fill(x, 1, 1))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "qrfact (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`QR`, the function being called here, only has one method:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "methods(QR)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "1 method for generic function <b>QR</b>:<ul><li> QR<i>{T}</i>(factors::<b>Array{T,2}</b>,\u03c4::<b>Array{T,1}</b>)</ul>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "# 1 method for generic function \"QR\":\n",
        "QR{T}(factors::Array{T,2},\u03c4::Array{T,1})"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It takes a matrix and a vector. Unfortunately, the second argument that `qrfact` passes in is a matrix and not a vector."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "typeof(fill(2.5,1,1))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "Array{Float64,2}"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This results in the following error:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "qrfact(2)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "ename": "LoadError",
       "evalue": "no method QR{T}(Array{Int64,2}, Array{Int64,2})\nwhile loading In[8], in expression starting on line 1",
       "output_type": "pyerr",
       "traceback": [
        "no method QR{T}(Array{Int64,2}, Array{Int64,2})\nwhile loading In[8], in expression starting on line 1",
        " in qrfact at In[5]:1"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "I created [issue #5923](https://github.com/JuliaLang/julia/issues/5923) to report the problem, and it is being fixed."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Missing `+`/`-` for `Triangular` type"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`check_method_calls` also found a pair of missing arithmetic functions on a special type of matrix. Julia has a set of special matrix types whose speicifc strutures allow doing some operations much more efficiently than a normal matrix. The `+`/`-` methods that take two different types from among these special types are generated by a for-loop; this probably made it easier to miss the lack of `(Triangle,Triangle)` methods to call.\n",
      "\n",
      "The following methods always throw `NoMethodError`s:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "-(Diagonal{T},Triangular{T<:Number})\n",
      "-(Triangular{T<:Number},Diagonal{T})\n",
      "-(Bidiagonal{T},Triangular{T<:Number})\n",
      "-(Triangular{T<:Number},Bidiagonal{T})\n",
      "-(Tridiagonal{T},Triangular{T<:Number})\n",
      "-(Triangular{T<:Number},Tridiagonal{T})\n",
      "-(SymTridiagonal{T},Triangular{T<:Number})\n",
      "-(Triangular{T<:Number},SymTridiagonal{T})\n",
      "+(Diagonal{T},Triangular{T<:Number})\n",
      "+(Triangular{T<:Number},Diagonal{T})\n",
      "+(Bidiagonal{T},Triangular{T<:Number})\n",
      "+(Triangular{T<:Number},Bidiagonal{T})\n",
      "+(Tridiagonal{T},Triangular{T<:Number})\n",
      "+(Triangular{T<:Number},Tridiagonal{T})\n",
      "+(SymTridiagonal{T},Triangular{T<:Number})\n",
      "+(Triangular{T<:Number},SymTridiagonal{T})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The missing methods were:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "-(Triangular{T<:Number},Triangular{T<:Number})\n",
      "+(Triangular{T<:Number},Triangular{T<:Number})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": []
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "I filed this as [issue #5927](https://github.com/JuliaLang/julia/issues/5927), and it is being fixed."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Helper Functions"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "While introspecting on functions is surprisingly easy, there is a lot of ugly code created by the unfortunate structure of the `Expr` type. I wrote a number of helper functions to make my code clear. `code_typed` is a function from Julia's standard library; all functions from `TypeCheck` and all functions with implementations shown are ones I wrote."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "A Function to Retrieve Return Types"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`code_typed` returns `Expr`s that have lots of type annotations, including the return type of the function. There is a consistent structure to the `Expr`s that are returned.\n",
      "If we call the `Expr` from `code_typed` `e`, then `e.head` will be `:lambda` and `e.typ` will be `Any`.\n",
      "The third element of `e.args` will be another `Expr`; let's call this one `e2`.\n",
      "`e2.head` will be `:body`; `e2.typ` will be set to the inferred return type of the function. (There is currently no syntax in Julia to annotate function return types.)"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "code_typed(foo,(Int,))[1].args[3].typ"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "Int64"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Because this is not especially readable, I wrote a helper function to pull out the return type:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": true,
     "input": [
      "returntype(e::Expr) =  e.args[3].typ"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "returntype (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "heading",
     "level": 4,
     "metadata": {},
     "source": [
      "Usage examples:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For a call to `code_typed` that we know will have one method returned:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "returntype(code_typed(foo,(Int,))[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "Int64"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For calls that might have more than one result:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "Type[returntype(t) for t in code_typed(+,(Number,))]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "2-element Array{Type{T<:Top},1}:\n",
        " Int64 \n",
        " Number"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "map(returntype,code_typed(+,(Any,Any,Any)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 13,
       "text": [
        "3-element Array{Any,1}:\n",
        " BigInt  \n",
        " BigFloat\n",
        " Any     "
       ]
      }
     ],
     "prompt_number": 13
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "A Function to Retrieve All Expression in the Function Body"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To continue with the names `e` and `e2` from above, `e2.args` will be an `Array` of `Expr`s representing the body of the function. This is frequently useful when analyzing functions, but also cryptic. `body(e)` is a function to wrap this structural access in a readable name."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "body(e::Expr) = e.args[3].args"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 14,
       "text": [
        "body (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 14
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It is used analogously to `returntype` above."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "body(code_typed(foo,(Int,))[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "4-element Array{Any,1}:\n",
        " :( # In[2], line 2:)                                     \n",
        " :(z = top(box)(Int64,top(add_int)(x::Int64,5))::Int64)   \n",
        " :( # line 3:)                                            \n",
        " :(return top(box)(Int64,top(mul_int)(2,z::Int64))::Int64)"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "A Function to Retrieve All Return Statements From a Function"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It is also common to want to grab only a particular subset of `Expr`s from the function body. One possibility is the return statements.\n",
      "`Expr`s that represent return statements have `head` set to `:return`, so the below function pulls them out of the body."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "returns(e::Expr) =\n",
      "    filter(x-> typeof(x) == Expr && x.head==:return,body(e))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 16,
       "text": [
        "returns (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "returns(code_typed(foo,(Int,))[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 17,
       "text": [
        "1-element Array{Any,1}:\n",
        " :(return top(box)(Int64,top(mul_int)(2,z::Int64))::Int64)"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function barr(x::Int)\n",
      "    x + 2\n",
      "end\n",
      "\n",
      "returns(code_typed(barr,(Int,))[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 18,
       "text": [
        "1-element Array{Any,1}:\n",
        " :(return top(box)(Int64,top(add_int)(x::Int64,2))::Int64)"
       ]
      }
     ],
     "prompt_number": 18
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Notice that we still get a `:return`, even if we don't use the keyword `return`. The last expression in a function becomes the return value if there is no `return`, and this is expressed in the AST by desugaring to a normal `:return`."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Other Helper Functions"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The above functions demonstrate the general structure of the helper functions I wrote. There are other helper functions that I wrote used in the rest of this writeup; they will all be namespaced with `TypeCheck`. In Julia, `using TypeCheck` imports this module, making the functions available."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "using TypeCheck"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 19
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Checking for Stable Return Types"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It is good style in Julia for the return type of a method to only depend on the types of the arguments and not on their values.\n",
      "This stability makes behavior more predictable for programmers.\n",
      "It also allows type inference to work better -- stable types on called methods allows stable types on the variables you put the return values into."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The following method is a simple example of an unstable return type.\n",
      "Sometimes it returns an `Int` and sometimes a `Bool`.\n",
      "The return type of this method would be inferred as `Union(Int64,Bool)`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function unstable(x::Int)\n",
      "  if x > 5\n",
      "    return x\n",
      "  else\n",
      "    return false\n",
      "  end\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 20,
       "text": [
        "unstable (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "unstable(5)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "false"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "unstable(1337)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 22,
       "text": [
        "1337"
       ]
      }
     ],
     "prompt_number": 22
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Until now, there has been no way to automatically check that methods do not behave in this way.\n",
      "Julia's base library is mostly free of this, through the use of code review.\n",
      "While there are instances of instability, they tend to be less obvious -- they stem especially from retrieving data from untyped storage, from some interfaces to other environments, or from places where it is necessary (higher-level functions)."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "I have written a static checker to detect that this invariant may be violated. It's not perfect."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Results"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "While this check works well for many methods with type annotations on their arguments, it assumes all methods without type annotations are fine. It also passes some methods that have arguments annotated with abstract types that do depend on argument values."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "True Positive:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`check_return_types` lists the methods that failed, and their return types. Methods whose arguments are annotated with concrete types work the best with this check."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "TypeCheck.check_return_types(unstable)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "(Int64)::Union(Int64,Bool)\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 23,
       "text": [
        "unstable"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "foo1(x::Int) = isprime(x) ? x: false\n",
      "TypeCheck.check_return_types(foo1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "(Int64)::Union(Int64,Bool)\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "foo1"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "False Negative:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Any method that does not annotated its argument types will pass. Some, including the example below, should definitely not pass:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "foo2(x) = isprime(x) ? x : false\n",
      "check_return_types(foo2) # no printing means it passed"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 25,
       "text": []
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Deciding Whether the Return Type is Probably Stable"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There are three kinds of types in Julia: concrete, abstract, and union. Every value in Julia has a concrete type. Therefore, a method that returns a concrete type must be stable. Abstract and union types have zero or more concrete types as subtypes; a return type that is not concrete could be unstable. For example, `foo`, above, has a return type of `Union(Int64,Bool)`.\n",
      "\n",
      "The types of the arguments to a method are of the same three kinds. If any of the arguments are not concrete, then the return type might need to change for different subtypes. For example, `+(x::Number,y::Number)` could reasonably return `Number`: it makes sense for `+(5,10)` to return an `Int64` and `+(4.2,5.4)` to return a `Float64`. However, if all the arguments have concrete types (or there are no arguments), then the type should be concrete: there is no excuse for it to change."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Concrete, Abstract, and Union Types"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "I've already mentioned concrete and abstract types, which are the leaves and internal nodes of the type hierarchy, respectively. Union types are collection of types. They are similar to abstract types in that they have subtypes, but they do not have names and do not alter the type hierarchy. Union types provide a way to say \"Any of these types or their subtypes\"."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[Int, String, Union(Float64,UTF8String)]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 26,
       "text": [
        "3-element Array{Type{T<:Top},1}:\n",
        " Int64                    \n",
        " String                   \n",
        " Union(UTF8String,Float64)"
       ]
      }
     ],
     "prompt_number": 26
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Unlike concrete and abstract types, union types are not represented by `DataType`; they have their own type, `UnionType`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "[typeof(x) for x in ans]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 27,
       "text": [
        "3-element Array{Type{_},1}:\n",
        " DataType \n",
        " DataType \n",
        " UnionType"
       ]
      }
     ],
     "prompt_number": 27
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In the standard library, there is a convenient function for differetiating between concrete types and all other types: `isleaftype`.\n",
      "It returns true for concrete types (the leaves of the type hierarchy) and false for abstract types and union types."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isleaftype(Uint128)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 28,
       "text": [
        "true"
       ]
      }
     ],
     "prompt_number": 28
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isleaftype(String)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 29,
       "text": [
        "false"
       ]
      }
     ],
     "prompt_number": 29
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isleaftype(Union(Int,Float32,ASCIIString))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 30,
       "text": [
        "false"
       ]
      }
     ],
     "prompt_number": 30
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "The Basic Check"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "We can check that the return type of a method is based on the types of its arguments rather than their values by examining the types of the arguments and the return type.\n",
      "If the return type is concrete, then everything is fine: a concrete type can't be unstable.\n",
      "If the return type is not concrete and at least one argument is not concrete, then the method gets the benefit of the doubt that the return type is varying based on the argument type.\n",
      "If the return type is not concrete, but all the argument are concrete, then the method will fail the check."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function isreturnbasedonvalues(e::Expr)\n",
      "  rt = returntype(e)\n",
      "  ts = TypeCheck.argtypes(e) #type of each argument in e's type signature\n",
      "\n",
      "  if isleaftype(rt) || rt == None\n",
      "    return false\n",
      "  end\n",
      "\n",
      "  for t in ts\n",
      "   if !isleaftype(t)\n",
      "     return false\n",
      "   end\n",
      "  end\n",
      "\n",
      "  return true # return is not concrete type; all args are concrete types\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 31,
       "text": [
        "isreturnbasedonvalues (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 31
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isreturnbasedonvalues(code_typed(unstable,(Int,))[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 32,
       "text": [
        "true"
       ]
      }
     ],
     "prompt_number": 32
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isreturnbasedonvalues(code_typed(foo,(Int,))[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 33,
       "text": [
        "false"
       ]
      }
     ],
     "prompt_number": 33
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "While this check works on simple examples, it tends to have many false-positives when running on large modules, such as the standard library."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Preventing One Unstable Function from Spawning Many More Warnings"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The simple function above gives many warnings about functions in the Base library. This is caused by a propagation of return types. If a method of `f2` does some work and then ends with a call to `f1`, the return type of `f2` is determined by `f1`. If `f1` has an unstable return type, then `f2` will also -- despite `f2` behaving well.\n",
      "\n",
      "While `f2` does literal have an unstable return type, any change to fix things should really happen in `f1`. This makes warning about `f2` unhelpful. Wading through hundreds of warnings to find the actual method to change is frustrating. This sea of warnings can be drained by adding a second chance for otherwise-failing functions. Methods like `f2` can be filtered out by looking at the `:return`s in the function body and letting them pass if their return type is determined by `:call`s to other functions (which are unstable). While this simple change would catch `return f1(2)` but not `x = f1(2); return x`, in practice this change has be sufficient."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "A Example of Return Type Propagation"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To give a full example, here is an unstable `f1` getting called by `f2`, where `f2` is doing nothing wrong beyond calling `f1`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "f1(x::Int) = x == 5 ? 42 : pi\n",
      "returntype(code_typed(f1,(Int,))[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 34,
       "text": [
        "Union(Int64,MathConst{:\u03c0})"
       ]
      }
     ],
     "prompt_number": 34
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "f2(y::Int) = f1(y + 2)\n",
      "returntype(code_typed(f2,(Int,))[1])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 35,
       "text": [
        "Union(Int64,MathConst{:\u03c0})"
       ]
      }
     ],
     "prompt_number": 35
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Preventing Propagation"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "To give methods a second chance, we can add another section between checking the argument types and returning `true`. Only methods that would have previously failed will encounter this new code."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function isreturnbasedonvalues(e::Expr)\n",
      "    rt = returntype(e)\n",
      "    ts = TypeCheck.argtypes(e)\n",
      "\n",
      "    if isleaftype(rt) || rt == None\n",
      "      return false\n",
      "    end\n",
      "    for t in ts\n",
      "     if !isleaftype(t)\n",
      "       return false\n",
      "     end\n",
      "    end\n",
      "\n",
      "    #a second chance\n",
      "    #cs is a list of return types for calls in :return exprs in e's body\n",
      "    cs = [TypeCheck.returntype(c,e) \n",
      "            for c in TypeCheck.extract_calls_from_returns(e)]\n",
      "    for c in cs\n",
      "      if rt == c # e's returntype == the call's returntype\n",
      "         return false\n",
      "      end\n",
      "    end\n",
      "\n",
      "    return true #e fails the test\n",
      "  end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 36,
       "text": [
        "isreturnbasedonvalues (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 36
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There are two helper functions from `TypeCheck` used above.\n",
      "\n",
      "* `extract_calls_from_returns(e)` examines the `:return` statements in `e` and pulls out any `:call`s they contain. It returns the `:call` `Expr`s in an `Array`.\n",
      "* `find_returntype(call,context)` tries to determine the return type of the `call`, given the `context` (the method) it's being called in.\n",
      "\n",
      "The implementation of `find_returntype` is explained in detail below."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Results:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isreturnbasedonvalues(code_typed(foo,(Int,))[1])\n",
      "#passes, correctly foo(Int)::Int"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 37,
       "text": [
        "false"
       ]
      }
     ],
     "prompt_number": 37
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isreturnbasedonvalues(code_typed(f1,(Int,))[1])\n",
      "#fails, correctly f1(Int)::Union(Int64,MathConst{:\u03c0})"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 38,
       "text": [
        "true"
       ]
      }
     ],
     "prompt_number": 38
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "isreturnbasedonvalues(code_typed(f2,(Int,))[1])\n",
      "#passes, to prevent propagation from f1"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 39,
       "text": [
        "false"
       ]
      }
     ],
     "prompt_number": 39
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Determining the Return Type of a `:call`"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The job of `find_returntype` is to take an `Expr` with head `:call` and determine the return type of that function call. Sometimes that type has already been annotated, which makes it easy. Occasionally, it is necessary to examine the possible methods than could be called and make a `Union` of their return types."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "call = TypeCheck.extract_calls_from_returns(code_typed(f2,(Int,))[1])[1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 40,
       "text": [
        ":(f1(top(box)(Int64,top(add_int)(y::Int64,2))::Int64)::Union(Int64,MathConst{:\u03c0}))"
       ]
      }
     ],
     "prompt_number": 40
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`call` is an `Expr`; `call.head` is `:call`. This indicates that `call.args` will have a specific structure.\n",
      "`call.args[1]` will be the function being called; the remainder of `call.args` (in this case, just `call.args[2]`) will be the arguments."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "println(call.args[1])\n",
      "println(call.args[2])"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "f1\n"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        ":("
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "top(box)(Int64,top(add_int)(y::Int64,2))::Int64)\n"
       ]
      }
     ],
     "prompt_number": 41
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There is another helper function, whose implementation will be discussed later, that I wrote to determine the types of `Expr`s used as arguments to `:call`s. This can be used here to determine the type of things like `call.args[2]`. In this case, the type is already inferred:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "call.args[2].args[2]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 42,
       "text": [
        ":Int64"
       ]
      }
     ],
     "prompt_number": 42
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In fact, for `call`, we can just use the return type that type inference has already provided: `Union(Int64,MathConst{:\u03c0})`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "call.typ"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 43,
       "text": [
        "Union(Int64,MathConst{:\u03c0})"
       ]
      }
     ],
     "prompt_number": 43
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`call` is an example of the most common kind of expression that `find_returntype` handles. However, there are several other similar types of `Expr`s; they are handeled analogously, but the code has to be slightly different to handle their different structures.\n",
      "\n",
      "The code below starting with `if isdefined(Base,callee)` handles looking for matching methods if the return type has not already been annotated. Because `:call` only has a `Symbol` of the function name, we need to `eval` the `Symbol` to get an actual `Function` value. This `Function` value is then used to search through the methods for matches to this `:call`'s argument types, using the filtering of the built-in `code_typed` function."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function returntype(e::Expr,context::Expr) #must be :call,:new,:call1\n",
      "  if Base.is_expr(e,:new); return e.typ; end\n",
      "  if Base.is_expr(e,:call1) && isa(e.args[1], TopNode); return e.typ; end\n",
      "  if !Base.is_expr(e,:call); error(\"Expected :call Expr\"); end\n",
      "\n",
      "  if is_top(e)\n",
      "    return e.typ\n",
      "  end\n",
      "\n",
      "  callee = e.args[1]\n",
      "  if is_top(callee)\n",
      "    return returntype(callee,context)\n",
      "  elseif isa(callee,SymbolNode)\n",
      "    # (func::F), so an anonymous function\n",
      "    return Any\n",
      "  elseif isa(callee,Symbol)\n",
      "    if e.typ != Any ||\n",
      "            any([isa(x,LambdaStaticData) for x in e.args[2:end]])\n",
      "      return e.typ\n",
      "    end\n",
      "\n",
      "    if isdefined(Base,callee)\n",
      "      f = eval(Base,callee)\n",
      "      if !isa(f,Function) || !isgeneric(f)\n",
      "        return e.typ\n",
      "      end\n",
      "      fargtypes = tuple([argtype(ea,context) for ea in e.args[2:end]])\n",
      "      return Union([returntype(ef) for ef in code_typed(f,fargtypes)]...)\n",
      "    else\n",
      "      return @show e.typ\n",
      "    end\n",
      "  end\n",
      "\n",
      "  return e.typ\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 44,
       "text": [
        "returntype (generic function with 2 methods)"
       ]
      }
     ],
     "prompt_number": 44
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Stable Types Inside Loops"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In Julia, for-loops are generally the fastest way to write code. (Faster than vectorized code; faster than maps or folds.)\n",
      "One easy way to accidentally decrease their performance is to change the type of a variable during the loop.\n",
      "If all the variables in a loop have stable types, then the code Julia outputs will be the same fast code as a statically typed, compiled language.\n",
      "If a variable has a type that changes, slower dynamic code will be produced to handle that.\n",
      "It can be easy to write code that has this problem, if you're not aware of it, even in simple programs."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = 5 # x is an Int\n",
      "for i=1:1000\n",
      " x += 100\n",
      " x /= 2 # x is a Float64\n",
      "end \n",
      "x #x is a Float64"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 45,
       "text": [
        "100.0"
       ]
      }
     ],
     "prompt_number": 45
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "In this code example, `x` begins life as an `Int`. In the first iteration of the loop, `x += 100` takes `x` as an `Int` and returns an `Int`; `x /= 2` takes this new `Int` and returns a `Float64`. After this, `x` will be a `Float64` for all the remaining iterations of the loop. For each of the two function calls (`+` and `/`) code will be produced to check if the type of `x` and proceed accordingly. The extra code slows down every iteration, despite only being needed for the first one. This slow down can be removed by making `x` a `Float64` from the start: `x = 5.0`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "x = 5.0 # x is a Float64\n",
      "for i=1:1000\n",
      " x += 100\n",
      " x /= 2 # x is a Float64\n",
      "end \n",
      "x #x is a Float64"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 46,
       "text": [
        "100.0"
       ]
      }
     ],
     "prompt_number": 46
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Results"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Before presenting the implementation details, here are some examples of this check's performance."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "True Positives:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is the same example from above; `x` is an `Int64` sometimes and a `Float64` at others, all within the loop."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function barr1()\n",
      "  x=4\n",
      "  for i in 1:10\n",
      "    x *= 2.5\n",
      "  end\n",
      "  x\n",
      "end\n",
      "TypeCheck.check_loop_types(barr1)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "()::Union(Int64,Float64)\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "\tx::Union(Int64,Float64)\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 47,
       "text": [
        "barr1"
       ]
      }
     ],
     "prompt_number": 47
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "True Negatives:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If `x` becomes a `Float64` before entering the loop, then it does not trigger this warning."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function barr2()\n",
      "  x = 4\n",
      "  x = 2.5\n",
      "  for i=1:10\n",
      "    x *= 2.5\n",
      "  end\n",
      "end\n",
      "TypeCheck.check_loop_types(barr2) #no printing means it passed"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 48,
       "text": []
      }
     ],
     "prompt_number": 48
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If `x` stays the same type (`Int`) during the loop, but becomes a `Float64` afterwards, then it passes this check."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function barr3()\n",
      "    x = 4\n",
      "    for i = 1:10\n",
      "        x += i\n",
      "    end\n",
      "    x /= 2\n",
      "end\n",
      "TypeCheck.check_loop_types(barr3)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 49,
       "text": []
      }
     ],
     "prompt_number": 49
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If the variable `x` is annotated with type `Int` in a local function, then Julia will throw an error if a non-`Int` value would be assigned to `x`. Therefore, the function `barr4` below will throw an error rather than change `x`'s type. This means that no extra code will be generated to handle dynamic typing, so there is no instability here. This function also passes this check."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function barr4()\n",
      "  x::Int = 4\n",
      "  for i=1:10\n",
      "    x *= 2.5\n",
      "  end       \n",
      "end\n",
      "TypeCheck.check_loop_types(barr4)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 50,
       "text": []
      }
     ],
     "prompt_number": 50
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Why There Are No False Positives or False Negatives Listed Here"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It would be better to have false positive and/or negatives here, but I have yet to come up with an example that does not work. This check is based entirely on the type inference already being done by Julia; this code just looks at the inferred types of the variables. These inferred types are the same ones that the code generator is using to optimize. If the type of a variable is a concrete type, then the code generator will generate fast code. If the type of a variable is not concrete, then the generated code will handle multiple possible types. This check has the same information as the code generator, which allows it to accurately anticipate what code will be generated."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Implementation Details:"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Variables with unstable types can be detected in generic functions by looking at the output of `code_typed`.\n",
      "Since loops are lowered to gotos, we need to first find the loops and then check the types of the variables involved.\n",
      "Finding loops can be as simple as looking for gotos that jump backwards in the function: gotos whose labels precede them.\n",
      "Each instruction between the goto and its label is part of the loop body.\n",
      "For each instruction in the loop body, we can look at the inferred type of any variables involved.\n",
      "If the inferred type is a UnionType (or not a leaf type), then the variable's type is unstable.\n",
      "\n",
      "The high-level version looks like this:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "check_loop_types(e::Expr;kwargs...) =\n",
      "    TypeCheck.loosetypes(e,TypeCheck.loopcontents(e))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 51,
       "text": [
        "check_loop_types (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 51
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There are two new helper functions here:\n",
      "\n",
      "* `loopcontents(e)` returns all of the `Expr`s from `body(e)` that are inside loops. The implementation is straight-forward, and thus not discussed further here.\n",
      "* `loosetypes(context,exprs)` finds any variables that occur in `exprs` that have unstable (`Union`) types. The implementation of this function is detailed below."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Finding Loose Types"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There are two parts to `loosetypes`: finding all the variables in output of `loopcontents` and deciding if those variables has loose types.\n",
      "Most of the code in `loosetypes` is a series of loops for digging into each `Expr` to find any variables.\n",
      "The \"unstable type\" test comes in the line `elseif typeof(e1) == SymbolNode && !isleaftype(e1.typ) && typeof(e1.typ) == UnionType`.\n",
      "\n",
      "Variables are `Symbol`s; when they are annotated with a type, the `Symbol` and type are packaged together into `SymbolNode`. All variables in type inferred code are become `SymbolNode`s. If `e1` is a `SymbolNode`, then it's type is `e1.typ`. The rest of that conditional checks that the type is not a concrete type and is a `UnionType`."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      " function loose_types(method::Expr,lr::Vector)\n",
      "    lines = (Symbol,Type)[]\n",
      "    for (i,e) in lr\n",
      "      if typeof(e) == Expr\n",
      "        es = copy(e.args)\n",
      "        while !isempty(es)\n",
      "          e1 = pop!(es)\n",
      "          if typeof(e1) == Expr\n",
      "            append!(es,e1.args)\n",
      "          elseif typeof(e1) == SymbolNode && !isleaftype(e1.typ)\n",
      "                    && typeof(e1.typ) == UnionType\n",
      "            push!(lines,(e1.name,e1.typ))\n",
      "          end \n",
      "        end                          \n",
      "      end\n",
      "    end\n",
      "    return LoopResult(MethodSignature(method),lines)\n",
      "  end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 52,
       "text": [
        "loose_types (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 52
    },
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Statically Detecting `NoMethodError`s"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Julia's closest equivalent to compile-time type errors is the `NoMethodError`. This occurs when you try to call a function, but no method exists to handle that combination of arguments. `\"stop\" + 2` would throw a `NoMethodError`, for example, because there is no method that works for `+(String,Int)`.\n",
      "\n",
      "These runtime errors can be especially annoying in rarely run code, or code that is only run after a long computation. It is an obviously useful application of static analysis.\n",
      "\n",
      "This detection cannot be done exactly because methods can be added at any time. There is always a possibility that the necessary method will, in fact, get added before the call occurs. (This means that zero false positives would not be possible.)\n",
      "\n",
      "A high-level view of the implementation is:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "check_method_calls(e::Expr;kwargs...) =\n",
      "    TypeCheck.no_method_errors(e,TypeCheck.method_calls(e);kwargs...)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 53,
       "text": [
        "check_method_calls (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 53
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It combines:\n",
      "\n",
      "* `method_calls(e)`, which filters `:call` `Expr`s out of the body of `e` and transforms them into a function name and argument types. While `method_calls` is not interesting enough to show in more detail, it uses a helper function `argtype` to identify the types of arguments to the function being called; `argtype`'s implementation is explained below.\n",
      "* `no_method_errors`, which takes the output of `method_calls`, calls `hasmatches` on each one, and collects any failures. This is just glue code, so it's implementation will not be detailed here. However, `hasmatches` is interesting. It takes one call's signature and tries to find any matching methods. This is where the actual analysis occurs, so the implementation is described below."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "False Positives"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Near the beginning of this writeup, I listed issues and pull requests made to the Julia standard library; several are from the check and can serve as true positives. There are a few known remaining problems with this check, which I will explain with the false positive examples below."
     ]
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "Namespace Issues"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "TypeCheck.check_method_calls(transpose)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "(SparseMatrixCSC{Tv,Ti})::SparseMatrixCSC{Tv,Ti<:Integer}\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "transpose!(SparseMatrixCSC{Tv,Ti},SparseMatrixCSC{Tv,Ti<:Integer})\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "\t"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 54,
       "text": [
        "transpose"
       ]
      }
     ],
     "prompt_number": 54
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This is claiming that there is no `transpose!(SparseMatrixCSC{Tv,Ti},SparseMatrixCSC{Tv,Ti<:Integer})`; however, it only checks in the `Base` module because `transpose` is exported from `Base`. The relevant `transpose!` is in `Base.SparseMatrix`:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "methods(Base.SparseMatrix.transpose!)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "1 method for generic function <b>transpose!</b>:<ul><li> transpose!<i>{Tv,Ti}</i>(S::<b>SparseMatrixCSC{Tv,Ti}</b>,T::<b>SparseMatrixCSC{Tv,Ti}</b>) at <a href=\"https://github.com/JuliaLang/julia/tree/840c1fbe418c4741836aec48b462b9149e579d85/base/sparse/csparse.jl#L126\" target=\"_blank\">sparse/csparse.jl:126</a></ul>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 55,
       "text": [
        "# 1 method for generic function \"transpose!\":\n",
        "transpose!{Tv,Ti}(S::SparseMatrixCSC{Tv,Ti},T::SparseMatrixCSC{Tv,Ti}) at sparse/csparse.jl:126"
       ]
      }
     ],
     "prompt_number": 55
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This could be fixed by somehow finding what module a method is implemented in (regardless of where the method is exported) and looking there for implementations of the methods being called. I don't know how to find out what module a method is implemented in.\n",
      "\n",
      "The otherside of this problem, a false negative, can be demonstracted by a self-contained example:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "module FalseNegative\n",
      "  export problem\n",
      "  problem() = functionthatdoesntexist()\n",
      "end\n",
      "TypeCheck.check_method_calls(FalseNegative)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": []
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "The total number of failed methods in FalseNegative is 0\n"
       ]
      }
     ],
     "prompt_number": 56
    },
    {
     "cell_type": "heading",
     "level": 3,
     "metadata": {},
     "source": [
      "`MIME{mime}`"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "There are a set of functions in Julia that form a system for displaying types in custom ways. They center around a `MIME{mime}` type and `writemime` that takes a `MIME` type and a value to display. `check_method_calls` fails the versions of these functions that take strings and convert them to `MIME` types. For example:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "TypeCheck.check_method_calls(mimewritable)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "(String,Any)::Bool\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "mimewritable(Type{_<:MIME{mime}},Any)\n"
       ]
      },
      {
       "metadata": {},
       "output_type": "display_data",
       "text": [
        "\t"
       ]
      },
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 57,
       "text": [
        "mimewritable"
       ]
      }
     ],
     "prompt_number": 57
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "methods(mimewritable)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "html": [
        "2 methods for generic function <b>mimewritable</b>:<ul><li> mimewritable<i>{mime}</i>(::<b>MIME{mime}</b>,x) at <a href=\"https://github.com/JuliaLang/julia/tree/840c1fbe418c4741836aec48b462b9149e579d85/base/multimedia.jl#L37\" target=\"_blank\">multimedia.jl:37</a><li> mimewritable(m::<b>String</b>,x) at <a href=\"https://github.com/JuliaLang/julia/tree/840c1fbe418c4741836aec48b462b9149e579d85/base/multimedia.jl#L42\" target=\"_blank\">multimedia.jl:42</a></ul>"
       ],
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 58,
       "text": [
        "# 2 methods for generic function \"mimewritable\":\n",
        "mimewritable{mime}(::MIME{mime},x) at multimedia.jl:37\n",
        "mimewritable(m::String,x) at multimedia.jl:42"
       ]
      }
     ],
     "prompt_number": 58
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "This example is clearly incorrect because the `MIME` version will accept any `MIME` type you could construct. The relevant definitions from the Base library are shown below:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "MIME(s) = MIME{symbol(s)}()\n",
      "mimewritable(m::String, x) = mimewritable(MIME(m), x)\n",
      "mimewritable{mime}(::MIME{mime}, x) =\n",
      "  method_exists(writemime, (IO, MIME{mime}, typeof(x)))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 58
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`mimewritable(String,Any)` usings `MIME(Any)` to convert the `String` into a `Symbol` and then calls `mimewritable(MIME, Any)`. Unfortunately, my code currently infers `MIME(Any)` to produce `Type{_<:MIME{mime}}`. This type is not the same as `MIME{mime}`, which would actually work."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Identifying Argument Types"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`argtype` expects to get an AST node that is in the `args` of a `:call`. This could be another function call, a variable name, or a literal value.\n",
      "\n",
      "Literal values are pretty straight forward to type:"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "argtype(n::Number,e::Expr) = typeof(n)\n",
      "argtype(c::Char,e::Expr) = typeof(c)\n",
      "argtype(s::String,e::Expr) = typeof(s)\n",
      "argtype(l::LambdaStaticData,e::Expr) = Function\n",
      "argtype(i,e::Expr) = typeof(i)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 59,
       "text": [
        "argtype (generic function with 5 methods)"
       ]
      }
     ],
     "prompt_number": 59
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "For variables, there are two ways they can show up. If they are just a symbol, then I try looking them up in the surrounding `Expr`, which knows about function arguments and local and captured variables."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function argtype(s::Symbol,e::Expr)\n",
      "  vartypes = [x[1] => x[2] for x in e.args[2][2]]\n",
      "  s in vartypes ? (vartypes[s]) : Any\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 60,
       "text": [
        "argtype (generic function with 6 methods)"
       ]
      }
     ],
     "prompt_number": 60
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The other case is easier. As mentioned in the section on checking variable types in loop above, some variables come packaged with their inferred types as `SymbolNode`s."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "argtype(s::SymbolNode,e::Expr) = s.typ"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 61,
       "text": [
        "argtype (generic function with 7 methods)"
       ]
      }
     ],
     "prompt_number": 61
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`QuoteNode`s wrap some other `Expr`(s), so their type is the type of their value. `TopNode`s are a representation of intrinsic functions; these occur as funtion names in `:call`s, so they should usually get handled there. There's nothing to do with just the name, all we can do is return `Any` for these."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "argtype(q::QuoteNode,e::Expr) = find_argtype(q.value,e)\n",
      "argtype(t::TopNode,e::Expr) = Any"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 62,
       "text": [
        "argtype (generic function with 9 methods)"
       ]
      }
     ],
     "prompt_number": 62
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "The last case is when I get an `Expr`. Usually, this is a `:call`. This represents something like `foo(2+2)`, where `find_method_calls` is trying to type `foo`'s argument, `+(2,2)`. Here, we want the return type of `+(2,2)`, so I call `find_returntype`, which I described earlier when talking about checking the stability of function return types."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function argtype(e::Expr,context::Expr)\n",
      " if Base.is_expr(e,:call) || Base.is_expr(e,:new) || Base.is_expr(e,:call1)\n",
      "   return returntype(e,context)\n",
      " end\n",
      " return Any\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 63,
       "text": [
        "argtype (generic function with 10 methods)"
       ]
      }
     ],
     "prompt_number": 63
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "If the return type of `+(2,2)` is not already annotated, `find_returntype` would, in turn, call `find_argtype` on `2` and `2`, in order to examine the correct method of `+`."
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Checking Method Calls"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "`hasmatches` takes three things:\n",
      "\n",
      "* the `Module` containing the function that is making the call\n",
      "* the `Symbol` of the function name\n",
      "* an `Array` containing the type of each argument used\n",
      "\n",
      "`hasmatches` either returns `true` if there are methods that could match this call or `false` if none exist."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "function hasmatches(mod::Module,cs::TypeCheck.CallSignature)\n",
      "    if isdefined(mod,cs.name)\n",
      "      f = eval(mod,cs.name)\n",
      "      if isgeneric(f)\n",
      "        opts = methods(f,tuple(cs.argtypes...))\n",
      "        if isempty(opts)\n",
      "          return false\n",
      "        end\n",
      "      end\n",
      "      return true\n",
      "   end\n",
      "end"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "metadata": {},
       "output_type": "pyout",
       "prompt_number": 64,
       "text": [
        "hasmatches (generic function with 1 method)"
       ]
      }
     ],
     "prompt_number": 64
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "It does this check by taking the `Symbol` of the function name and `eval`ing it to get an actual `Function`. (This doesn't always work because some functions are not top-level and cannot be found by `eval`ing; warning about these causes too many false-positives.) Then, as long as `f` is a generic, named function, `f` is checked for matching methods using built-in `methods` function. `methods` takes a `Function` and a tuple of argument types and returns an `Array` of matching methods. If the result is empty, then the call fails the check."
     ]
    }
   ],
   "metadata": {}
  }
 ]
}